from typing import List

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []
        ans = []
        m, n = len(matrix), len(matrix[0])
        left, right, top, bottom = 0, n - 1, 0, m - 1
        while left <= right and top <= bottom:
            for i in range(left, right + 1):
                ans.append(matrix[top][i])
            for i in range(top + 1, bottom + 1):
                ans.append(matrix[i][right])
            for i in range(right - 1, left -1, -1):
                if top < bottom:
                    ans.append(matrix[bottom][i])
            for i in range(bottom - 1, top, -1):
                if left < right:
                    ans.append(matrix[i][left])
            left, right, top, bottom = left + 1, right - 1, top + 1, bottom - 1
            
        return ans


class Solution2:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []
        res=matrix[0]
        matrix=[list(x) for x in zip(*matrix[1:])][::-1]
        res+=self.spiralOrder(matrix)
        return res
